package sword.T33;

import util.TreeNode;

import java.util.*;

/**
 * @Author: duyuzhou
 * @Create: 2022-04-07 16:37:56 星期四
 */

class Solution {

    private boolean flag = true;

    public boolean verifyPostorder(int[] postorder) {
        int[] inorder = new int[postorder.length];
        System.arraycopy(postorder, 0, inorder, 0, postorder.length);
        Arrays.sort(inorder);
        create(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);
        return flag;
    }

    private void create(int[] inorder, int[] postorder, int ileft, int iright, int pleft, int pright) {
        if (!flag ||ileft > iright)
            return;
        int k = -1;
        for (int i=ileft; i<=iright; ++i) {
            if (inorder[i] == postorder[pright]) {
                k = i;
                break;
            }
        }
        if (k < 0) {
            flag = false;
            return;
        }
        int len = k - ileft;
        create(inorder, postorder, ileft, k-1, pleft, pleft+len-1);
        if (!flag)
            return;
        create(inorder, postorder, k+1, iright, pleft+len, pright-1);
    }
}